//
// Created by mac on 2023/11/23.
//

// 将 x 减到 0 的最小操作数
class Solution
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        // 1、初始化
        int sum = 0;
        for(const auto e : nums) sum += e;
        int target = sum - x;
        // 2、细节处理(数组中所有元素都大于0，所以 target 小于 0 是不存在的)
        if(target < 0) return -1;
        // 3、滑动窗口
        int ret = -1;
        for(int left = 0, right = 0, tmp = 0; right < nums.size();)
        {
            // 进窗口
            tmp += nums[right++];
            // 出窗口
            while(tmp > target) tmp -= nums[left++];
            // 更新结果
            if(tmp == target) ret = max(ret, right - left);
        }
        // 4、返回结果
        return ret == -1 ? ret : nums.size() - ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

// 最大连续 1 的个数III
class Solution
{
public:
    int longestOnes(vector<int>& nums, int k)
    {
        // 1、初始化
        int n = nums.size();
        int ret = INT_MIN;
        // 2、滑动窗口
        int left = 0, right = 0;
        int length = 0; // 当前子数组中最长连续 1 的长度
        int zero = 0;  // 当前子数组中 0 出现的次数
        while(right < n)
        {
            if(nums[right] != 0) // nums[right] 非 0，此时 right 一定入窗口
            {
                ret = max(ret, ++length);
                ++right;
            }
            else
            {
                if(zero + 1 <= k)
                {
                    ret = max(ret, ++length);
                    ++zero;
                    ++right;
                }
                else
                {
                    if(nums[left++] == 0)  --zero;
                    --length;
                }
            }
        }
        // 3、返回值
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

// 无重复字符的最长子串
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        // 1、初始化
        int n = s.size();
        vector<int> count(256);
        int left = 0, right = 0, ret = 0;
        // 2、滑动窗口
        int length = 0; //用来记录窗口长度
        while(right < n)
        {
            if(!count[s[right]]) //进窗口
            {
                ++count[s[right]];
                ++length;
                ++right;
                ret = max(ret, length); //更新结果
            }
            else //出窗口
            {
                --count[s[left]];
                --length;
                ++left;
            }
        }
        // 3、返回值
        return ret;
    }
};
/*
- 时间复杂度：O(n)
- 空间复杂度：O(1)
*/

//
